<html>
<head><meta charset="utf-8"><title>BTreeMap::from_ordered_iter? · t-libs · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/index.html">t-libs</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html">BTreeMap::from_ordered_iter?</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="191830260"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191830260" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191830260">(Mar 26 2020 at 01:02)</a>:</h4>
<p>Suppose I have an iterator of key-value pairs that promises to provide values in increasing order by key. Would that allow constructing a BTreeMap more efficiently?</p>



<a name="191852568"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191852568" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191852568">(Mar 26 2020 at 08:40)</a>:</h4>
<p>Possibly.</p>



<a name="191855624"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191855624" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191855624">(Mar 26 2020 at 09:11)</a>:</h4>
<p>I'm tempted to try rewriting btree, possibly taking a few ideas from <a href="https://abseil.io/blog/20190812-btree" title="https://abseil.io/blog/20190812-btree">https://abseil.io/blog/20190812-btree</a>. I had a quick look and the main difference is that they have much larger node sizes.</p>



<a name="191855699"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191855699" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191855699">(Mar 26 2020 at 09:11)</a>:</h4>
<p>The main issue with the current implementation is that it tries to use lifetimes, but that just doesn't work when you're trying to build a datastructure.</p>



<a name="191855759"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191855759" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191855759">(Mar 26 2020 at 09:12)</a>:</h4>
<p>The code is much less efficient than it could be.</p>



<a name="191917295"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191917295" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191917295">(Mar 26 2020 at 17:05)</a>:</h4>
<p><span class="user-mention" data-user-id="143274">@Amanieu</span> I would <em>love</em> to see a more efficient <code>BTreeMap</code>, and would deeply appreciate it.</p>



<a name="191917398"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191917398" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191917398">(Mar 26 2020 at 17:06)</a>:</h4>
<p>Happy to test; I may have some large performance test cases in a few weeks.</p>



<a name="191917559"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191917559" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Josh Triplett <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191917559">(Mar 26 2020 at 17:07)</a>:</h4>
<p>So, you're thinking of switching over to raw pointers and entirely unsafe internals?</p>



<a name="191917687"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191917687" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191917687">(Mar 26 2020 at 17:08)</a>:</h4>
<p>The lifetimes don't really help much with unsafety currently -- there's no raw references to speak of in the structs -- and I'm not sure what specifically <span class="user-mention" data-user-id="143274">@Amanieu</span> is referring to.</p>



<a name="191917761"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191917761" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191917761">(Mar 26 2020 at 17:09)</a>:</h4>
<p>(Well, I mean, they're only real help is they mean you can't wander off completely detached, but doing so in practice is quite hard anyway, certainly you're not going to start spawning a thread or w/e. The actual data is all behind raw pointers so the lifetimes don't help you there).</p>



<a name="191917928"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191917928" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191917928">(Mar 26 2020 at 17:11)</a>:</h4>
<p>I also don't know exactly what we mean by "much less efficient than it could be" -- but I wouldn't disagree with it either, it's not implausible. I've not attempted to do performance analysis, though we've been steadily trying to clean up the existing impl a bit over the past month or so</p>



<a name="191917942"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191917942" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191917942">(Mar 26 2020 at 17:11)</a>:</h4>
<p>(IMO, that has gone pretty well.)</p>



<a name="191927933"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191927933" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191927933">(Mar 26 2020 at 18:18)</a>:</h4>
<p>The main issue is that <code>marker::Mut&lt;'a&gt;</code> only allows you to have one active <code>NodeRef</code> at a time. So the code has to go through hoops when it wants to mutate multiple nodes at once.</p>



<a name="191928126"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191928126" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191928126">(Mar 26 2020 at 18:20)</a>:</h4>
<p>It's easier to explain with a linked list as an example. Let's say you want to remove the next node of a linked list. You call <code>list_remove(current-&gt;next)</code> and <code>list_remove</code> will unlink the next node from its two neighbors. But the compiler doesn't know that <code>current-&gt;next-&gt;prev == current</code> so it has to reload the pointer from memory even though it is probably already in a register.</p>



<a name="191928209"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191928209" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191928209">(Mar 26 2020 at 18:20)</a>:</h4>
<p>This could be avoided if the code was a bit more liberal with lifetimes.</p>



<a name="191928332"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191928332" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191928332">(Mar 26 2020 at 18:21)</a>:</h4>
<p>Have a look at this to see what I mean by a <code>Cell</code>-based design: <a href="https://github.com/Amanieu/intrusive-rs/blob/master/src/rbtree.rs" title="https://github.com/Amanieu/intrusive-rs/blob/master/src/rbtree.rs">https://github.com/Amanieu/intrusive-rs/blob/master/src/rbtree.rs</a></p>



<a name="191928512"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191928512" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191928512">(Mar 26 2020 at 18:23)</a>:</h4>
<p>All operations on <code>NodePtr</code> take <code>self</code> (since <code>NodePtr: Copy</code>) and can freely mutate the <code>next</code>/<code>prev</code>/<code>parent</code> pointers which are wrapped in <code>Cell</code>s.</p>



<a name="191928710"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191928710" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191928710">(Mar 26 2020 at 18:24)</a>:</h4>
<p>(This code was written before <code>NonNull</code> was stabilized, so it could be improved by making <code>NodePtr</code> non-null and wrapping it in an option)</p>



<a name="191930273"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191930273" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191930273">(Mar 26 2020 at 18:36)</a>:</h4>
<p><span class="user-mention" data-user-id="143274">@Amanieu</span> That's not true, you can <code>reborrow_mut()</code> and get another NodeRef.</p>



<a name="191930381"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191930381" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191930381">(Mar 26 2020 at 18:37)</a>:</h4>
<p>But yes, more generally, I want to drop that lifetime because I don't think it buys us much</p>



<a name="191930438"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191930438" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191930438">(Mar 26 2020 at 18:37)</a>:</h4>
<p>I'm not sure if a rewrite is necessary, though -- I think it should be relatively straightforward to refactor the current code. It's my next planned project, in fact, if no one beats me to it.</p>



<a name="191930570"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191930570" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191930570">(Mar 26 2020 at 18:38)</a>:</h4>
<p>You're right, a rewrite is probably overkill.</p>



<a name="191930954"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191930954" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191930954">(Mar 26 2020 at 18:41)</a>:</h4>
<p>I've been looking at Google's btree implementation: <a href="https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/btree.h" title="https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/btree.h">https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/btree.h</a></p>



<a name="191931345"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191931345" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Amanieu <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191931345">(Mar 26 2020 at 18:44)</a>:</h4>
<p>They have a few interesting tricks:</p>
<ul>
<li>The number of nodes depends on the size of <code>T</code>. They use <code>constexpr</code> to aim for a leaf node size of ~256 bytes. This means that with <code>sizeof(T) == 4</code> they have a B of 61.</li>
<li>If the tree only has a root leaf node, it may use a smaller allocation. The root node's allocation grows (via realloc) until it reaches B. All other nodes have a full allocation size.</li>
<li>A pointer to the leftmost and rightmost leaf node is cached for faster iteration.</li>
</ul>



<a name="191931778"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191931778" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191931778">(Mar 26 2020 at 18:48)</a>:</h4>
<p>The first and the last item seem relatively straightforward, and I'd be unopposed -- the realloc to grow the root node sounds quite painful to get right, in some sense in particular with Rust though</p>



<a name="191931826"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191931826" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191931826">(Mar 26 2020 at 18:49)</a>:</h4>
<p>(in particular, you would need to be even more careful about making references to that memory)</p>



<a name="191931916"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/BTreeMap%3A%3Afrom_ordered_iter%3F/near/191931916" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/BTreeMap.3A.3Afrom_ordered_iter.3F.html#191931916">(Mar 26 2020 at 18:49)</a>:</h4>
<p>It also sounds like the kind of niche optimization that is ill-suited for what we usually do in std, similar to SmallVec vs Vec</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>